package pers.qianyu.month_202101.date_20210123;

/**
 * 684. 冗余连接
 * https://leetcode-cn.com/problems/redundant-connection/
 *
 * @author mizzle rain
 * @date 2021-01-23 11:07
 */
public class FindRedundantConnection {
    private int[] p;

    private int find(int x) {
        while (p[x] != x) {
            p[x] = p[p[x]];
            x = p[x];
        }
        return x;
    }

    public int[] findRedundantConnection(int[][] edges) {
        int n = 1011;
        p = new int[n];
        for (int i = 0; i < n; i++) p[i] = i;

        for (int[] edge : edges) {
            int x = edge[0], y = edge[1];
            if (find(x) != find(y)) {
                p[find(x)] = find(y);
            } else {
                return edge;
            }
        }
        return new int[]{-1, -1};
    }
}
